package com.gy.algorithm.carl.linklistexa;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
 *
 * 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
 *
 * 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
 *
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl.linklistexa
 * @Author: gy
 * @Date: 2024/10/26 11:24
 * @Description:
 */
public class LRUCache146_advanced {
    public LRUCache146_advanced(int capacity) {
        this.capacity = capacity;
        this.head = new DoubleLink();
        this.tail = new DoubleLink();
        head.next = tail;
        tail.prev = head;
    }

    DoubleLink head;
    DoubleLink tail;
    int capacity = 0;
    int size = 0;
    Map<Integer,DoubleLink> cache = new HashMap<>();

    public int get(int key) {
        DoubleLink node = cache.get(key);
        if(node == null) return -1;

        // 每次获取都要放到头部
        moveToHead(node);
        return node.value;
    }

    private void moveToHead(DoubleLink node) {
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(DoubleLink node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    public void put(int key, int value) {
        DoubleLink node = cache.get(key);
        if(node == null){
            DoubleLink tmp = new DoubleLink(key, value);
            cache.put(tmp.key,tmp);
            addToHead(tmp);
            size++;
            
            if(size > capacity){
                DoubleLink tail = removeTail();
                cache.remove(tail.key);
                size--;
            }

        }else{
            node.value = value;
            moveToHead(node);
        }
    }

    private DoubleLink removeTail() {
        DoubleLink node = tail.prev;
        removeNode(node);
        return node;
    }

    private void removeNode(DoubleLink node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    class DoubleLink{
        DoubleLink prev;
        DoubleLink next;
        int key;
        int value;

        public DoubleLink(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public DoubleLink() {

        }
    }
}
